


import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map.Entry;

/**
 *
 * @author Eric Beaudry
 */
public class GenPolitique1 {
	public static final long TEMPS_LIMITE = 950; //950 millisecondes, donc un peu moins d'une seconde
    public static HashMap<ActionType, HashMap<Integer,Double>> PossibilityOfActions; //Repr�sente le type d'action (1er cl�), la possibilit� d'action (2eme cl�) et sa probabilit� (value)
	public static long tempsDepart;
	public static final Integer COST_OF_MOVE  = 1;
    
    public static PolitiqueSimple generate(Plateau p){
    	tempsDepart = System.currentTimeMillis();
        PolitiqueSimple pol = new PolitiqueSimple(p.nbCases);
        int R[] = new int [p.getNbCases()];
        double V[] = new double [p.getNbCases()];
        
        initiateValue(p,R,V);
        initiatePossibilities();
    	while(resteTemps()){
    		V = completeAnIteration(p,R,V,pol);
    	}
        return pol;
    }
    
    public static double[] completeAnIteration(Plateau p, int R[], double V[],PolitiqueSimple pol){
    	double VPrime[] = new double[p.getNbCases()];
    	
    	for(int i = 0; i < p.getNbCases() && resteTemps(); i++){
    		int valueOfAction = 0;
    		double valueOfLastAction = Double.MAX_VALUE;
    		for(ActionType action: PossibilityOfActions.keySet()){
    			valueOfAction = 0;
    			for(Integer movement : PossibilityOfActions.get(action).keySet()){
    				valueOfAction += (V[p.getNextCase(i, movement)] * PossibilityOfActions.get(action).get(movement));
    			}
    			if(valueOfAction < valueOfLastAction){
    				valueOfLastAction = valueOfAction;
    				pol.actions[i] = action;
    				VPrime[i] = (double) R[i] + COST_OF_MOVE + valueOfLastAction;
    			}
    		}
    	}
    	
    	return VPrime;
    }

	private static boolean resteTemps() {
		return System.currentTimeMillis() - tempsDepart < TEMPS_LIMITE;
	}
    
    public static void initiateValue(Plateau p, int R[], double V[]){
    	for(int i = 0; i < p.getNbCases(); i++){
    		V[i] = 0.0;
    		R[i] = 0;
    	}
    	R[p.getNbCases() - 1] =  -p.getNbCases();
    }
    
    public static void initiatePossibilities(){
    	PossibilityOfActions = new HashMap<ActionType, HashMap<Integer,Double>>();
    	//Action 1 : 1
    	PossibilityOfActions.put(ActionType.UneSeuleCase, new HashMap<Integer, Double>());
    	PossibilityOfActions.get(ActionType.UneSeuleCase).put(1, 1.0);
    	//Action 2 : 1 d�
    	HashMap<Integer, Double> unSeulDe = new HashMap<Integer, Double>();
    	for(int i = 1; i <= 6; i++){
    		unSeulDe.put(i, 1.0/6.0);
    	}
    	PossibilityOfActions.put(ActionType.UnDe, unSeulDe);
    	//Action 3 : 2 d�s
    	HashMap<Integer, Double> deuxDe = new HashMap<Integer, Double>();
    	deuxDe.put(2, 1.0/36.0);
    	deuxDe.put(3, 2.0/36.0);
    	deuxDe.put(4, 3.0/36.0);
    	deuxDe.put(5, 4.0/36.0);
    	deuxDe.put(6, 5.0/36.0);
    	deuxDe.put(7, 6.0/36.0);
    	deuxDe.put(8, 5.0/36.0);
    	deuxDe.put(9, 4.0/36.0);
    	deuxDe.put(10, 3.0/36.0);
    	deuxDe.put(11, 2.0/36.0);
    	deuxDe.put(12, 1.0/36.0);
    	PossibilityOfActions.put(ActionType.DeuxDes, deuxDe);
    }
    

    public static void main(String args[]) throws Exception {
        Plateau plateau = Plateau.load(new InputStreamReader(System.in));
        PolitiqueSimple pol = generate(plateau);
        OutputStreamWriter out = new OutputStreamWriter(System.out);
        PolitiqueSimple.save(pol, out);
        out.close();
    }
}
